import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreeP {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
             this.val = val;
        }
    }

    //根节点
    TreeNode root;

    public static List<Integer> preorderTraversal(TreeNode root) {
        //首先定义一个List<Integer>
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        //如果root == null
        if(root == null) {
            return result;
        }

        //开始遍历，利用栈保存已经遍历的结点
        TreeNode cur = root;

        //前序遍历：根左右
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                //将结点的值放入List之中
                result.add(cur.val);
                //将结点放入栈之中
                stack.push(cur);

                cur = cur.left;
            }
            //代码走到这里，说明根节点和左子树都访问完了，此时需要访问右子树
            //弹出栈顶元素，让cur等于栈顶元素的右孩子
            TreeNode tmp = stack.pop();
            cur = tmp.right;
        }

        return result;
    }

    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        //需要一个prev判断栈顶元素是否被遍历过

        if (root == null) {
            return result;
        }

        TreeNode prev = null;

        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                //将当前结点压入栈
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                result.add(top.val);
                stack.pop();
                prev = top;
            } else {
                cur = top.right;
            }
        }
        return result;
    }


    public  static int i = 0;
    //父接口
    public  static TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root =  buildTreeImpl(preorder,inorder,0,preorder.length - 1);
        return root;
    }

    //真正实现
    public static TreeNode buildTreeImpl(int[] preorder,int[] inorder,int beginindex,int overindex) {
        //递归出口
        if(beginindex > overindex) {
            return null;
        }

        //构造根节点
        TreeNode root = new TreeNode(preorder[i]);
        int curIndex = i;
        i++;

        int inIndex = -1;
        //遍历中序遍历序列
        for(int j = beginindex;j <= overindex;j++) {
            if(inorder[j] ==  preorder[curIndex]) {
                inIndex = j;
                break;
            }
        }

        //构造root的左子树
        root.left = buildTreeImpl(preorder,inorder,beginindex,inIndex - 1);
        //构造root的右子树
        root.right = buildTreeImpl(preorder,inorder,inIndex + 1,overindex);

        return root;
    }

    public int j ;
    public  TreeNode buildTreeByPostOrder(int[] inorder, int[] postorder) {
        //处理空值
         if(postorder.length == 0 && inorder.length == 0) {
             return null;
         }
         j = postorder.length - 1;
        return buildTreeByPostOrderImpl(inorder,postorder,0,postorder.length - 1);
    }

    public  TreeNode buildTreeByPostOrderImpl(int[] inorder,int[] postorder,int beginIndex,int overIndex) {
        //递归出口
        if (beginIndex > overIndex) {
            return null;
        }


        TreeNode root = new TreeNode(postorder[j]);
        j--;


        int inIndex = -1;
        //在中序遍历中寻找当前的结点
        for (int j = beginIndex; j <= overIndex; j++) {
            if (inorder[j] == root.val) {
                inIndex = j;
                break;
            }
        }

        //递归构造root的右孩子
        root.right = buildTreeByPostOrderImpl(inorder, postorder, inIndex + 1, overIndex);
        //递归构造root的左孩子
        root.left = buildTreeByPostOrderImpl(inorder, postorder, beginIndex, inIndex - 1);

        return root;
    }

    public static String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        if(root == null) {
            return stringBuilder.toString();
        }

        tree2StrImpl(root,stringBuilder);

        return stringBuilder.toString();
    }

    public static void tree2StrImpl(TreeNode root,StringBuilder stringBuilder) {
        if(root == null) {
            return;
        }

        //先将当前节点的值append到stringBuilder的后面
        stringBuilder.append(root.val);

        //判断root的左右子树的情况开始递归处理
        if(root.left != null) {
            //添加左括号
            stringBuilder.append("(");
            //递归处理左子树
            tree2StrImpl(root.left,stringBuilder);
            //添加右括号
            stringBuilder.append(")");
        }else {
            //判断右子树是否为空
            if(root.right != null) {
                stringBuilder.append("()");
            }else {
                return;
            }
        }

        if(root.right != null) {
            //递归处理子树
            stringBuilder.append("(");
            tree2StrImpl(root.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }
    public static void main(String[] args) {
        BinaryTreeP binaryTreeP = new BinaryTreeP();
        binaryTreeP.root = new TreeNode(1);
        binaryTreeP.root.left = new TreeNode(2);
        binaryTreeP.root.right = new TreeNode(3);
        binaryTreeP.root.left.left = new TreeNode(4);

        System.out.println(tree2str(binaryTreeP.root));
    }
}
